package com.swak.algs;

import com.swak.algs.node.TreeNode;

import lombok.Getter;
import lombok.Setter;
import lombok.ToString;
import lombok.experimental.Accessors;

/**
 * 是否搜索二叉树: 左子树最大值 <= 他 => 右子树最小值
 * 
 * @author lifeng
 */
public class Code12 {

	@Getter
	@Setter
	@Accessors(chain = true)
	@ToString
	static class Info {
		boolean bs;
		int max;
		int min;
	}

	static Info isSearchBinary(TreeNode head) {
		if (head == null) {
			return null;
		}
		Info info = new Info();
		Info leftInfo = isSearchBinary(head.left);
		info.max = leftInfo == null ? head.val : Math.max(head.val, leftInfo.max);
		Info righInfo = isSearchBinary(head.right);
		info.min = righInfo == null ? head.val : Math.min(head.val, righInfo.min);
		return info.setBs(head.val >= info.max && head.val <= info.min);
	}

	public static void main(String[] args) {
		TreeNode root = TreeNode.newBlanceTree();
		System.out.println(isSearchBinary(root));
		root = TreeNode.newSearchTree();
		System.out.println(isSearchBinary(root));
	}
}
